package com.jn.algorithm.day011.question32;

/**
 * @author 江南大学1033190417
 * @date 2022/4/26 11:11
 */
public class Solution {


    //动态规划
    public int longestValidParentheses(String s) {
        int maxRes = 0;
        int length = s.length();
        int[] dp = new int[length];
        for (int i = 1; i < length; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
                } else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = i - dp[i - 1] - 2 >= 0 ? dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 : dp[i - 1] + 2;
                }
            }
            maxRes = Math.max(maxRes, dp[i]);
        }
        return maxRes;
    }

    /*
       申明两个变量left,right
     */
    public int longestValidParentheses2(String s) {
        int left = 0, right = 0, maxRes = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == '(')
                ++left;
            else
                ++right;
            if (left == right) {
                maxRes = Math.max(maxRes, left * 2);
            }
            if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = length - 1; i >= 0; i--) {
            if (s.charAt(i) == '(')
                ++left;
            else
                ++right;
            if (left == right) {
                maxRes = Math.max(maxRes, left * 2);
            }
            if (right < left) {
                left = right = 0;
            }
        }

        return maxRes;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestValidParentheses2("(()"));
    }
}
